package com.yun.algorithm.divideandconquer.leetcode;

import java.util.concurrent.ThreadLocalRandom;

public class FindKthLargestLeetcode215 {
    public int findKthLargest(int[] a, int k) {
        return quickSelect(a, 0, a.length - 1, a.length - k);
    }

    private int quickSelect(int[] a, int left, int right, int k) {
        int p = partition(a, left, right);
        if (p == k) {
            return a[p];
        } else if (k<p) {
            return quickSelect(a, left, p - 1, k);
        } else {
            return quickSelect(a, p + 1, right, k);
        }
    }

    private int partition(int[] a, int left, int right) {
        int idx = ThreadLocalRandom.current().nextInt(right - left + 1)+left;
        swap(a,idx,left);
        int pv=a[left];
        int i=left;
        int j=right;
        while (i<j){
            while (i<j&&a[j]>pv){
                j--;
            }
            while (i<j&&a[i]<=pv){
                i++;
            }
            swap(a,i,j);
        }
        swap(a,left,i);
        return i;
    }

    private void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    public static void main(String[] args) {
        int[] a = {3, 2, 1, 5, 6, 4};
        int k = 2;
        FindKthLargestLeetcode215 res = new FindKthLargestLeetcode215();
        System.out.println(res.findKthLargest(a, k));
    }
}
